package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * 有一只跳蚤的家在数轴上的位置 x 处。请你帮助它从位置 0 出发，到达它的家。
 * 跳蚤跳跃的规则如下：
 * 它可以 往前 跳恰好 a 个位置（即往右跳）。
 * 它可以 往后 跳恰好 b 个位置（即往左跳）。
 * 它不能 连续 往后跳 2 次。
 * 它不能跳到任何 forbidden 数组中的位置。
 * 跳蚤可以往前跳 超过 它的家的位置，但是它 不能跳到负整数 的位置。
 * 给你一个整数数组 forbidden ，其中 forbidden[i] 是跳蚤不能跳到的位置，
 * 同时给你整数 a， b 和 x ，请你返回跳蚤到家的最少跳跃次数。如果没有恰
 * 好到达 x 的可行方案，请你返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-jumps-to-reach-home
 */
public class 到家的最少跳跃次数_1654 {

    public static void main(String[] args) {

        System.out.println(minimumJumps(new int[]{8, 3, 16, 6, 12, 20}, 15, 13, 11));

    }

    /**
     * 广度优先搜索
     */
    public static int minimumJumps(int[] forbidden, int a, int b, int x) {
        Set<Integer> forbiddenSet = new HashSet<>();
        for (int i : forbidden) {
            forbiddenSet.add(i);
        }
        boolean[] visited = new boolean[4000 + b];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{0, 0});
        visited[0] = true;

        int minJumps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int[] pre = queue.pollFirst();
                int curX = pre[0];
                if (pre[0] == x) {
                    return minJumps;
                }
                // 不能连续两次往后跳
                if (curX - b > 0 && !visited[curX - b] && !forbiddenSet.contains(curX - b) &&
                        pre[1] != -1) {
                    queue.addLast(new int[]{curX - b, -1});
                    visited[curX - b] = true;
                }

                if (curX + a < 4000 + b && !visited[curX + a] && !forbiddenSet.contains(curX + a)) {
                    queue.addLast(new int[]{curX + a, 1});
                    visited[curX + a] = true;
                }
            }
            minJumps++;
        }
        return -1;
    }

}
